package 差分与前缀和;

import java.util.Arrays;

public class 前缀和与差分法 {
    public static void main(String[] args) {
        int[] arr = new int[]{0, 1, 2, 3, 4, 5, 7, 2};
        //前缀和
        int[] diff = new int[arr.length];

        for (int i = 1; i < diff.length; i++) {
            diff[i] = arr[i] - arr[i - 1];
        }
        System.out.println("原数组" + Arrays.toString(arr));

        System.out.println(Arrays.toString(diff));
        diff_num(diff, 2, 5, 3);
        System.out.println(Arrays.toString(diff));
        diff_fu_yuan(diff);
        System.out.println(Arrays.toString(diff));
    }

    public static void diff_num(int[] diff, int l, int r, int num) {
        diff[l] = diff[l] + num;
        diff[r + 1] = diff[r + 1] - num;
    }

    public static void diff_fu_yuan(int[] diff) {
        for (int i = 1; i < diff.length - 1; i++) {
            diff[i] = diff[i] + diff[i - 1];
        }
    }

}
